博弈论4 [杂题]

①[POJ 2975] Nim
原题链接:http://poj.org/problem?id=2975
题目大意:给定一个nn个石子,每次可以取kik_i个石子的NimNim游戏。问先手必胜的操作方案有几种。
数据范围:
多组测试数据
1n10001 \leq n \leq 1000
1ki1091 \leq k_i \leq 10^9
样例输入:

3
7 11 13
2
1000000000 1000000000
0

样例输出:

3
0

首先,如果异或和为00显然答案为0。
其次考虑有多少种方案使得初始状态能走到一个必败态:
即对于每一个kik_i来说,是否能移动若干个他里面的石子导致异或值到00。记异或和为SS,显然SS00,对于当前的某一个kik_i来说其他的异或和为SkiS \oplus k_i,若加上了与kik_i的异或和变成了00,则需要满足除去他之外的异或和是大于他的,即Ski<kiS \oplus k_i < k_i,当满足了这个条件之后,存在从kik_i里移动若干个石块使得他的数量变成SkiS \oplus k_i,使异或和变成0。
因此答案就是满足Ski<kiS \oplus k_i < k_i的数的个数。

②[POJ 3537]Crosses andCrosses
题目大意:有一个1n1*n的长条格子纸,每次可以往上画一个XX,最先连出三个的胜利。问是否先手必胜。
注意:原题面虽然没说,但是实际上本题是有多组测试数据的。
数据范围:
多组测试数据
1n20001 \leq n \leq 2000
样例输入:

3
6

样例输出:

1
2

可以发现,如果往某一个位置上填了,那么可以等价于前后两个连续的格子都不能放了,于是就可以把这个问题转换成多个有向图游戏的和。记忆化搜索分隔两边分别求救可以了。
不过这个题setset的效率会非常垃圾。用数组+memsetmemset
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2005;
int f[N],n;
int sg(int n)
{
	if(n <= 0)	return 0;
	if(f[n] != -1)	return f[n];
	bool st[n + 2];
	memset(st,0,sizeof st);
	for(int i = 1;i <= n;++i)
		st[sg(i - 3) ^ sg(n - i - 2)] = 1;
	int res = 0;
	while(st[res])	++res;
	return f[n] = res;	
}
int main(){
    memset(f,-1,sizeof f);
    while(~scanf("%d",&n))
    	puts(sg(n)?"1":"2");
    return 0;
}

③[Codeforces 138D]World of Darkraft
题目大意:有一nmn*m的格子纸,上面写有L,R,XL,R,X三种字符。每次可以选一个字符删去它的同时,如果是LL则删去左下右上的所有格子,如果是RR则删去右下左上的所有格子,如果是XX则同时视作LLRR。问是否先手必胜。
数据范围:1n,m201 \leq n,m \leq 20
样例输入:

2 2
RL
LR
2 2
RR
RR

样例输出:

LOSE
WIN

对角线上的操作难以分割状态,可以把整个棋局旋转45°45°,实际的坐标变换就是:(x,y)>(x+y,xy+m)(x,y) -> (x + y, x - y +m),映射结束之后,新的图上LL就是横向切一刀,RR就是纵向切一刀。同时整个棋局是可以二染色的,对于二染色之后的图来说,上面的不同颜色的点之间的状态是可以忽视的。因此可以分别求解。
在新图上,对应的坐标范围在(0,0)(0,0)(n+m,n+m)(n+m,n+m)之间。标记当前是找黑色的状态还是白色的状态,分别求出两个SGSG值,两者由于独立,异或和大于00就先手必胜。
关于这个题为什么入口的坐标可以取整个范围,我个人的理解是这个坐标只是一个范围,标记了整个图上的状态范围。可能这个范围偏大,但是不合法的坐标也不会计入。把范围放大一点可以避免有坐标没算进去。但是这个做法是有一点神棍元素,暂时没想到更好的精确的方法,如果想到了再更新内容。
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50;
char g[N][N];
int f[N][N][N][N][2];
int n,m;
int sg(int x1,int y1,int x2,int y2,int flag)
{
	if(x1 > x2 || y1 > y2)	return 0;
	if(f[x1][y1][x2][y2][flag] != -1)	return f[x1][y1][x2][y2][flag];
	bool st[400];
	memset(st,0,sizeof st);
	
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= m;++j)
		{
			int x = i + j,y = i - j + m;
			if((i + j & 1) == flag || x1 > x || x > x2 || y1 > y || y > y2)	continue;
			if(g[i][j] == 'L')	st[sg(x + 1,y1,x2,y2,flag) ^ sg(x1,y1,x - 1,y2,flag)] = 1;	
			if(g[i][j] == 'R')	st[sg(x1,y + 1,x2,y2,flag) ^ sg(x1,y1,x2,y - 1,flag)] = 1;
			if(g[i][j] == 'X')	st[sg(x + 1,y + 1,x2,y2,flag) ^ sg(x1,y1,x - 1,y - 1,flag) ^ sg(x + 1,y1,x2,y - 1,flag) ^ sg(x1,y + 1,x - 1,y2,flag)] = 1;
		}
	}
	
	int res = 0;
	while(st[res])	++res;
	return f[x1][y1][x2][y2][flag] = res;	
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(f,-1,sizeof f);
	for(int i = 1;i <= n;++i)	scanf("%s",g[i] + 1);
	if(sg(0,0,n + m,n + m,1) ^ sg(0,0,n + m,n + m,0))	puts("WIN");
	else puts("LOSE");
    return 0;
}